//
//  VarietySorted.swift
//  LeetCodeSwift
//
//  Created by XFB on 2019/8/6.
//  Copyright © 2019 XFB. All rights reserved.
//

import Foundation

class VarietySorted {
    
    
    /**
     冒泡排序
     1、首先将所有待排序的数组放入工作列表中
     2、重复2号步骤（倒数的数字加1.第一次到倒数第二个数字，第二次到倒数第三个数字，以此类推），直达再也不能交换
     平均时间复杂度：O(n^2)
     平均空间复杂度：O(1)
     */
    
    
    //MARK:- 1冒泡排序
    func BubbleSorted(_ nums: [Int]) -> [Int] {
        
        var array = nums
        var temp = 0
        for i in 0 ..< array.count - 1 {
            for j in 0 ..< array.count - 1 - i {
                if array[j] > array[j + 1] {
                    temp = array[j]
                    array[j] = array[j + 1]
                    array[j + 1] = temp
                }
            }
        }
        return array
    }
    
    /**
     插入排序
     1、从第一个元素开始，认为该元素已经是排好序的
     2、取下一个元素，在已经排好序的元素序列中 从后向前扫描
     3、如果已经排好序的序列中元素大于新元素，则将元素往右移动一个位置
     4、重复步骤3，直到已排好序的元素小于或等于新元素。
     5、在当前位置插入新元素。
     */
    
    //MARK:- 2插入排序 直接插入法1
    func InsertSorted(_ nums: [Int]) -> [Int] {
        
        var array = nums
        var temp = 0

        for i in 1 ..< array.count {
            temp = array[i]
            var j = i - 1
            while j >= 0 && array[j] > temp {
                array[j + 1] = array[j]
                j = j - 1
            }
            array[j + 1] = temp
        }
        return array
    }
    
    //MARK:- 2插入排序 直接插入法2
    func InsertSorted2(_ nums : [Int]) -> [Int] {
        
        var sortNums = nums
        for i in 1 ..< sortNums.count {
            var j = i
            let temp = sortNums[j]
            
            while j > 0 && temp < sortNums[j - 1] {
                /// 后移
                sortNums[j] = sortNums[j - 1]
                j = j - 1
            }
            sortNums[j] = temp
        }
        return nums
    }
    
    
    /**
     [5, 2, 6, 0, 9]
     1、low = 0, high = 0 中间下标 middle为 (low + high)/2 = 0
     2 < 5 成立，将high = 0-1 = -1
     j = i - 1 = 1 - 1 = 0
     j >= high + 1,  0 >= -1+1 = 0
     sortNums[0 + 1] = sortNums[0]
     j = - 1
     2 5 6 0 9
     
     2、low = 0, high = 1 中间下标 middle 为 (low + high)/2 = 0
     sortNum[i] = 6 > 2, low = middle + 1 = 1
     low = 1
     j = i - 1 = 2 - 1 = 1
     j = 1 >= high + 1 = 2 false
     sortNums[2] = temp = sortNums[2]

     */
    //MARK:- 折半插入法
    func InsertSorted3(_ nums : [Int]) -> [Int] {
        
        var sortNums = nums
        var temp = 0
        for i in 1 ..< sortNums.count {

            /// sortNums[i] 暂存在 temp
            temp = sortNums[i]
            
            /// 折半查找应该插入的位置
            var low = 0
            var high = i - 1
            
            /// 在 [low, high]中折半查找有序插入的位置
            /// low > high 说明没有关键字 等于 sortNums[i] 查找不成功
            /// 若相等查找成功 若不相等 缩小范围
            while low <= high {
                let middle = (low + high) / 2
                /// LQ <=    LT <
                /// 折半分区
                if sortNums[i] < sortNums[middle] {
                    /// 说明元素必在区间 [low, middle - 1]，所以令指针high 执行middle - 1 个元素
                    /// 插入点在低半区
                    high = middle - 1
                } else {
                    /// 说明元素必在区间 [middle + 1, high]，所以令指针 low 执行 middle + 1 个元素
                    /// 插入点在高半区
                    low = middle + 1
                }
            }
            
            /// 记录后移
            var j = i - 1
            while j >= (high + 1) {
                sortNums[j + 1] = sortNums[j]
                j = j - 1
            }
            /// 插入
            sortNums[high + 1] = temp
        }
        return sortNums
    }
    
    
    /**
     希尔排序(缩小增量排序) 属于插入排序类的方法
     先将整个待排记录序列分割成若干子序列分别进行插入排序，
     待整个序列中的记录 基本有序 时，在对整体记录进行一次直接插入排序
     
     子序列的构成不是简单地 逐段分割，而是将相隔某个 增量 的记录组成一个子序列
     
     */
    //MARK:- 4希尔排序
    func ShellSorted(_ nums: [Int]) -> [Int] {
        
        var sortNums = nums
        var step = nums.count / 2
        
        while step > 0 {
            for i in 0 ..< sortNums.count {
                let j = i + step
                print("\(j-step)")
                /// 18 < 17 不成立
                while j > step && j < sortNums.count {
                    if sortNums[j] < sortNums[j - step] {
                        let temp = sortNums[j]
                        sortNums[j] = sortNums[j - step]
                        sortNums[j - step] = temp
                    } else {
                        break
                    }
                }
            }
            step = step / 2
        }
        return sortNums
    }
    
    
    /**
     快速排序
     
     法一：
     /// 1、左标记右移，标记扫描到的值 > pivot, 左标记停止移动
     /// 2、右标记左移，标记扫描到的值 < pivot, 右标记停止移动
     /// 3、左右标记停止移动，交换左右标记扫描到的值
     /// 4、相同步骤继续
     /// 5、左右标记在同一位置，交换pivot的值
     
     法二：
     /// 1、i 慢指针、j 快指针
     /// 2、先移动 j 快指针，扫描到的值 < pivot, i 慢指针向右移动一位，并交换 i 和 j 扫描到的值
     /// 如果 i 和 j 在同一位置 不交换
     
     法三：
     通过一趟排序将待排记录分割成独立的两部分，一部分记录的关键字均比另一部分记录的关键字小
     则可分别对这两部分记录继续进行排序，以达到整个序列有序
     
     选择第一个 作为基准 pivot
     将所有关键字 较它小 的记录都安置在他的位置之前
     将所有关键字 较它大 的记录都安置在它的位置之后
     由此可以 该 基准记录最后 所落的位置 i 作为 分界线
     
     
     1、设置leftBound 和 rightBound  指针
     2、设置基准关键字 pivotKey
     3、从right 所指位置起向前搜索找到 第一个关键字 小于 pivot的记录和 基准记录位置交换
     3、从left  所指位置向后搜索，找到第一个关键字 大于 pivot 的记录和 基准记录位置交换
     4、重复上述操作，直到left == right
     */
    
    //MARK:- 3快速排序
    func QuickSorted(nums: inout [Int], leftBound : Int, rightBound : Int) {
        
        if leftBound >= rightBound {
            return
        }
                
        /// 第一个元素作为 基准点
        let pivotKey = nums[leftBound]
        var left = leftBound
        var right = rightBound
        
        /// 从表的两端交替的向中间扫描
        while left < right {
            while left < right && nums[right] >= pivotKey {
                right = right - 1
            }
            /// 比基准点记录小的值交换到低端
            nums[left] = nums[right]
            
            while left < right && nums[left] <= pivotKey {
                left = left + 1
            }
            /// 比基准点记录大的值交换到高端
            nums[right] = nums[left]
        }
        
        /// 基准点记录到位
        nums[left] = pivotKey
        
        /// 低字表 递归排序
        QuickSorted(nums: &nums, leftBound: leftBound, rightBound: left-1)
        /// 高字表 递归排序
        QuickSorted(nums: &nums, leftBound: left+1, rightBound: rightBound)
        
        print("\(nums)")
    }
    

    
    /**
     归并排序
     归并：两个或者两个以上的有序列表组合成一个新的有序表
     
     */
    //MARK:- 5归并排序1
    func MergeSorted(_ nums: [Int], _ L : Int, _ M : Int, _ R : Int) -> [Int] {
        
        var sortNums = nums
        
        let leftSize = M - L
        let rightSize = R - M + 1
        var leftArray = [Int]()
        var rightArray = [Int]()
        
        for i in 0 ..< M {
            leftArray.append(sortNums[i])
        }
        
        for i in M ... R {
            rightArray.append(sortNums[i])
        }
        
        var i = 0
        var j = 0
        var k = L
        
        while i < leftSize && j < rightSize {
            
            if leftArray[i] < rightArray[j] {
                sortNums[k] = leftArray[i]
                i = i + 1
                k = k + 1
            } else {
                sortNums[k] = rightArray[j]
                j = j + 1
                k = k + 1
            }
        }
        
        while i < leftSize {
            sortNums[k] = leftArray[i]
            i = i + 1
            k = k + 1
        }
        
        while j < rightSize {
            sortNums[k] = rightArray[j]
            j = j + 1
            k = k + 1
        }
        
        return sortNums
    }
    
    //MARK:- 5归并排序2
    func MergeSort(_ nums: [Int], _ L : Int, _ R : Int) -> [Int] {
        
        var sortNums = nums
        
        let M = (R - L) / 2
        
        let leftSize = M - L + 1
        let rightSize = R - M
        var leftArray = [Int]()
        var rightArray = [Int]()
        
        for i in 0 ... M {
            leftArray.append(sortNums[i])
        }
        
        for i in M+1 ... R {
            rightArray.append(sortNums[i])
        }
        
        var i = 0
        var j = 0
        var k = L
        
        while i < leftSize && j < rightSize {
            
            if leftArray[i] < rightArray[j] {
                sortNums[k] = leftArray[i]
                i = i + 1
                k = k + 1
            } else {
                sortNums[k] = rightArray[j]
                j = j + 1
                k = k + 1
            }
        }
        
        while i < leftSize {
            sortNums[k] = leftArray[i]
            i = i + 1
            k = k + 1
        }
        
        while j < rightSize {
            sortNums[k] = rightArray[j]
            j = j + 1
            k = k + 1
        }
        return sortNums
    }
   
}
